/**
 * Created With IntelliJ IDEA
 * Description:牛客网：BM67 不同路径的数目(一)
 * https://www.nowcoder.com/practice/166eaff8439d4cd898e3ba933fbc6358?tpId=295&tqId=685&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
 * User: DELL
 * Data: 2022-11-05
 * Time: 18:10
 */
import java.util.*;

//本题有三种解法，分别为递归，动态规划和数学组合排列
//这是动态规划解法
public class Solution {
    /**
     * @param m int整型
     * @param n int整型
     * @return int整型
     */
    public int uniquePaths (int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i < m + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                //只有一行或者只有一列的时候只有一种走法
                if (i == 1 || j == 1) {
                    dp[i][j] = 1;
                    continue;
                }
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m][n];
    }
}